package com.mrzhou.study.struct.linked;

/**
 *  实现单向环形队列链表(循环双链表结构):
 *      链表介绍: 见 classpath: doc/Java数据结构和算法.pdf 的4.5~4.6节
 */
public class AroundLinkedQueue<T> {

    private Node<T> front; // 初始节点, 这里不能创建头结点, 取数据时直接从头指针取, 插入时从头指针的上一位置插入
    private int size; // 环形队列链表的大小

    /**
     * 从头结点的上一节点后插入
     */
    public void add(T elem) {
        if (isEmpty()) {
           init(elem);
        } else {
            // 获取当前队列的上一节点, 并在此节点之后增加新节点
            Node<T> preNode = front.pre;
            Node<T> node = new Node<>(elem, preNode, this.front); // 创建新的节点
            preNode.next = node;
            this.front.pre = node;
        }
        size++;
    }

    public T get() {
        if(isEmpty()) {
            return null;
        }
        Node<T> cur = this.front;
        Node<T> preNode = this.front.pre;
        if(this.front.next == this.front) {
            this.front = null;
        } else {
            this.front = front.next; // 头指针下移
            this.front.pre = cur.pre;
            preNode.next = this.front;
        }
        cur.pre = null;
        cur.next = null;
        size--;
        return cur.elem;
    }

    public static void main(String[] args) {
        AroundLinkedQueue<Integer> queue = new AroundLinkedQueue<>();
        for(int i = 0; i < 100; i++) {
            queue.add(i);
        }
        int i = 1;
        while(!queue.isEmpty()) {
            if(i % 10 == 0) {
                System.out.print(queue.get() + "\n");
            } else {
                System.out.print(queue.get() + ", ");
            }
            i++;
        }
        System.out.printf("当前环形队列链表中####\n共有元素: %d个\n拥有的元素信息: %s\n", queue.size, queue);
    }

    private void init(T elem) {
        Node<T> node = new Node<>(elem, null, null);
        front = node;
        front.next = node;
        front.pre = node;
    }

    public boolean isEmpty() {
        return front == null;
    }

    public String toString() {
        StringBuffer sb = new StringBuffer("[");
        if(isEmpty()) {
            return sb.append(" ]").toString();
        }
        Node<T> current = this.front;
        while(current.next != this.front) {
            sb.append(current.elem).append(", ");
            current = current.next;
        }
        sb.append(current.elem);
        return sb.append("]").toString();
    }


    private class Node<T>{
        T elem; // 当前链表节点中的元素
        Node<T> next; // 链表的下一个节点的指针
        Node<T> pre; // 链表的上一个节点
        Node(T elem, Node<T> pre, Node<T> next) {
            this.elem = elem;
            this.pre = pre;
            this.next = next;
        }
    }

}
